1. Field of the Invention
The invention relates to retrieving pages of data stored in computer memory. More particularly, the invention relates to a method, apparatus, and article of manufacture for organizing pages of compressed data in computer memory for subsequent program execution.
2. Background of the Related Art
Flash memory is an adaptation of an electrically erasable programmable read-only memory (EEPROM), which may be erased and reprogrammed in blocks instead of one byte at a time. Flash Memory cards have increased in popularity because of the ease in updating the programs resident in the cards. Most personal computers (PC""s) have their basic input/output system (BIOS) stored in a flash memory module. Flash memory has also become popular in modems because it enables the modem manufacturer to support new protocols as they become standardized. Furthermore, some of the next generation workstations utilize flash memory to store programs such as an operating system and/or one or more application programs.
The cost of flash memory modules is directly related to the capacity of the modules. To reduce the capacity and associated costs of utilizing flash memory in a device, the files containing executable programs along with shared function libraries used by the executable programs may be compressed for example, via a compression buffer. The compression ratio increases as the amount of data in any compression xe2x80x9cclusterxe2x80x9d increases. For example, using a 64 KB cluster size yields approximately 60% compression such that a 1 MB file becomes a 400 KB file after compression.
Many memory management systems utilize a demand paging method to bring program instructions and data from virtual memory (e.g., flash memory) into Random Access Memory (RAM). Generally, demand paging is a type of swapping in which pages of data are copied from a storage source, such as a hard disk or flash memory, pages of data are copied from a storage source, such as a hard disk or flash memory, into the RAM as required. In particular, a computer system starts a program by retrieving the very first sections of the program from the file in the storage source, and then begins executing the program instructions in the retrieved sections. When an address of referenced data is not currently stored in the RAM, the processor generates a page fault, i.e., an interrupt. Upon triggering a page fault, a kernel page supervisor causes the missing page to be retrieved from the storage source. Once the page has been read into storage, the kernel page supervisor will allow the program to resume exactly where the program left off prior to the page fault.
In a memory management system utilizing demand paging, only the pages of the program that are actually needed to run the program are retrieved. Such memory management method generally reduces the amount of data transferred compared to some other types of memory management methods, which load all of the program instructions and data into storage before beginning program execution. As a result, demand paging substantially increases the operating efficiency of data processing systems and reduces the amount of high speed memory (e.g., RAM) needed to store instructions at any given time.
During further execution of the file, a problem arises when retrieving a required page located in the executable file when such file is compressed, because demand paging retrieves pages in a xe2x80x9crandom orderxe2x80x9d. In particular, when the next page event occurs, it is unlikely that the page requested is available within the block of pages that were previously decompressed and now reside within the RAM. As the executable file is processed, the operating system will initiate a page fault to retrieve the page of the executable file that is missing in the RAM. For example, in a compressed block containing 16 pages of data, the missing page that is required for further execution is stored along with 15 other compressed pages in one of a plurality of compressed blocks on the flash memory device. If the next page is not currently in the compression buffer, the set of pages currently in the compression buffer must be discarded. Thereafter, another compressed block of 16 pages must be retrieved from the storage source, decompressed, and the requested page extracted. In a worst case scenario for a 1 MB executable file, all 16 compressed blocks of pages would have to be decompressed once in a non-sequential order to retrieve one page from each 16-page block. As such, 32 KB (1024xc3x9732) of compressed data would have to be retrieved 256 times (16 pages/blockxc3x9716 block/file) resulting in 8,388,608 bytes (8 MB) of data being uncompressed.
Therefore, there is a need for a computer memory management system that efficiently utilizes demand paging on either decompressed or compressed data.
The present invention provides a method, article of manufacture, and apparatus for ordering a computer""s memory management system that utilizes demand paging on either decompressed or compressed data. One aspect of the invention provides, a method of ordering pages of data in a computer operating system during execution of a program file comprising a plurality of uncompressed pages of data. The method comprises tracing an execution of the plurality of uncompressed pages of data in a time ordered sequence and compressing the plurality of uncompressed pages into one or more blocks of compressed pages. Each of the plurality of uncompressed pages is then correlated with the one or more blocks of compressed pages in a relocation directory. The one or more blocks of compressed pages are then stored according to the time ordered sequence. In one embodiment, the method is embodied in a program contained on a computer-readable medium and is executable by a processor.
Another aspect of the invention provides a method of retrieving pages using a relocation directory during a page fault, wherein the relocation directory contains an access profile indicating the temporal order in which the pages were accessed for execution. The method comprises reading an offset and size of a requested page and determining whether a file containing the requested page is a compressed file. If the requested page is not compressed, the requested page is retrieved for execution. If the requested page is compressed, the offset of the requested page is translated to a value of a compressed block as defined in the relocation directory. The compressed block is then decompressed. In one embodiment, the method is embodied in a program contained on a computer-readable medium and is executable by a processor.
Yet another aspect of the invention provides an apparatus comprising a processor, volatile memory, a permanent storage device, a compression buffer, and a data structure residing in the permanent storage device. The data structure contains correlated values representing a plurality of pages in a compressed format and in an uncompressed format. The values of the plurality of pages are ordered according to when each of the plurality of pages in the uncompressed format was initially accessed by the processor during execution of a program.